/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ga.coordination;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;

/**
 *
 * @author hartono
 */
public class World {

    public Factory factory;
    public Truck truck;
    public char map[][];
    public byte rowMap;
    public byte columnMap;
    public byte totalAllMachine;
    public Machine machineList[];
    public HashMap<Character, Vendor> vendorList;
    public byte pathList[][][]; // 0 up, 1 right, 2 down, 3 left
    public static final byte PATH_UP = 0;
    public static final byte PATH_RIGHT = 1;
    public static final byte PATH_DOWN = 2;
    public static final byte PATH_LEFT = 3;
    public static final int INDEX_BFS = 0;
    public static final int INDEX_DFS = 2;
    public static final int INDEX_UCS = 3;
    public static final int INDEX_ASTAR = 4;
    public static final int INDEX_BESTFS = 5;
    public byte truckCapacity;
    public StringBuffer log;

    public World(File file) {
        factory = new Factory(this);
        vendorList = new HashMap<Character, Vendor>();
        pathList = new byte[92][92][];
        log = new StringBuffer();
        /*
        byte path [] = pathList[(int)'A'] [(int)'B'] ;
        
        pathLIst[a][b] = array of byte -> {1,2,0,1}
        pathLIs[a][c] = array byte -> {1,1,1,1,0}
        
        byte [] returnPath (int x1, int y1, int x2, int y2)
         * 
         */


        ReadInput(file);
    }

    /**
     * 
    Baris pertama 5 integer $, H, M, N, Y.
    M baris selanjutnya berisi spesifikasi dari setiap mesin. (T,W,S,P,I,C,R,Dependensi). Setiap spek dipisahkan oleh spasi.
    Dependensi -1 artinya independen
    
    Baris berikutnya berisi bilangan V, banyak vendor.
    V*2 baris berikutnya berisi nama dan nomor mesin yang disewakan vendor, dipisahkan dengan newline.
    Angka pertama pada baris nomor mesin menandakan jumlah nomor mesin.
    
    M baris berikutnya berisi harga produk ke-i
    
    Baris berikutnya berisi BARIS dan KOLOM dari peta. 
    BARIS baris berikutnya berisi string dengan panjang KOLOM dengan spesifikasi sbb:
    'P' -> Achmad
    'A'-'Z' -> vendor
    '.' -> jalan yang dapat dilalui
    '#' -> jalan yang tidak dapat dilalui
    (setiap karakter tidak dipisahkan spasi)
     * 
     * @param file 
     */
    public void ReadInput(File file) {
        try {
            BufferedReader buffReader = new BufferedReader(new FileReader(file));

            String row = buffReader.readLine();
            StringTokenizer st = new StringTokenizer(row, " ");

            // $ H M N Y
            long dollar;
            byte H, M, N, Y;
            dollar = Long.parseLong(st.nextToken());
            H = Byte.parseByte(st.nextToken());
            M = Byte.parseByte(st.nextToken()); // jumlah jenis mesin di dunia
            N = Byte.parseByte(st.nextToken()); // total mesin yang bisa disewa oleh pabrik
            Y = Byte.parseByte(st.nextToken()); // kapasitas truk
            factory.fund = dollar;
            factory.hour = H;
            factory.totalMachine = N;
            factory.idMachineList = new byte[M];

            truckCapacity = Y;
            truck = new Truck(Y);

            totalAllMachine = M;
            machineList = new Machine[M];

            // membaca M jenis mesin
            // (T,W,S,P,I,C,R,Dependensi)
            for (int i = 0; i < M; i++) {
                byte T, W, S, C, Depedensi;
                int I, P, R;
                row = buffReader.readLine();
                st = new StringTokenizer(row, " ");
                T = Byte.parseByte(st.nextToken());
//                System.out.println("EAAA " + i);
                W = Byte.parseByte(st.nextToken());
                S = Byte.parseByte(st.nextToken());
                P = Integer.parseInt(st.nextToken());
                I = Integer.parseInt(st.nextToken());
                C = Byte.parseByte(st.nextToken());
                R = Integer.parseInt(st.nextToken());
                Depedensi = (byte) (Byte.parseByte(st.nextToken()) - 1);
                // save ke struktur data
                Machine machine = new Machine();
                machine.idMachine = (byte) i;
                machine.hourPerDay = T;
                machine.hourPerPeriod = W;
                machine.sleep = S;
                machine.productivity = P;
                machine.productivityDefault = machine.productivity;
                machine.costOverload = C;
                machine.rentCost = R;
                machine.idDependency = Depedensi;
                machine.totalDependency = I;
                machineList[i] = machine;
            }

            byte V; // jumlah vendor
            row = buffReader.readLine();
            V = Byte.parseByte(row);

            for (int i = 0; i < V; i++) {
                char namaVendor; // nama vendor
                byte nMesin;// jumlah mesin;                
                row = buffReader.readLine(); // baris pertama
                namaVendor = row.charAt(0);
                row = buffReader.readLine(); // baris mesin yang disewakan
                st = new StringTokenizer(row, " ");
                nMesin = Byte.parseByte(st.nextToken());

                Vendor vendor = new Vendor();
                vendor.idVendor = namaVendor;
                vendor.totalMachineInVendor = nMesin;
                vendor.idMachineList = new byte[nMesin];
                for (int j = 0; j < nMesin; j++) {
                    byte tempId = (byte) (Byte.parseByte(st.nextToken()) - 1);
                    vendor.idMachineList[j] = tempId; // dikonvert dari 1 ke 0
                    machineList[tempId].idVendor.add(namaVendor);
                }
                vendorList.put(namaVendor, vendor);

            }
            // M baris berikutnya, harga produk ke - i 
            for (int i = 0; i < M; i++) {
                int hargaProduk;
                row = buffReader.readLine();
                hargaProduk = Integer.parseInt(row);
                // save ke struktur data                
                machineList[i].profitProduct = hargaProduk;
            }
            // baris dan kolom peta
            row = buffReader.readLine();
            byte rowMap, columnMap;
            st = new StringTokenizer(row, " ");
            rowMap = Byte.parseByte(st.nextToken());
            columnMap = Byte.parseByte(st.nextToken());
            this.rowMap = rowMap;
            this.columnMap = columnMap;
            map = new char[rowMap][columnMap];

            // baca width x height peta
            /*
            'P' -> Achmad
            'A'-'Z' -> vendor
            '.' -> jalan yang dapat dilalui
            '#' -> jalan yang tidak dapat dilalui
             */

            for (int i = 0; i < rowMap; i++) {
                row = buffReader.readLine();
                for (int j = 0; j < columnMap; j++) {
                    char tempElementMap;
                    tempElementMap = row.charAt(j);
                    map[i][j] = tempElementMap;

                    if (tempElementMap == 'P') {
                        factory.xPosition = (byte) i;
                        factory.yPosition = (byte) j;
                    } else if (tempElementMap == '.') {
                    } else if (tempElementMap == '#') {
                    } else {
                        Vendor tempVendor;
                        tempVendor = vendorList.get(tempElementMap);
                        if (tempVendor != null) {
                            tempVendor.xPosition = (byte) i;
                            tempVendor.yPosition = (byte) j;
                        }
                    }
                }
            }
            buffReader.close();
        } catch (Exception ex) {
            ex.printStackTrace();
        }

    }

    public StringBuffer PrintAllPairShortesPath() {
        StringBuffer ret = new StringBuffer("Path\n");
        for (int i = 65; i < 92; i++) {
            if (i != 80) {
                for (int j = i + 1; j < 92; j++) {
                    if (pathList[i][j] != null) {
                        ret.append((char) (i) + " - " + (char) (j) + " = " + pathList[i][j].length + " = {");
                        for (int k = 0; k < pathList[i][j].length; k++) {
                            ret.append(pathList[i][j][k] + " ");
                        }
                        ret.append("}\n");
                    }
                }
            } else {
                for (int j = 65; j < 92; j++) {
                    if (pathList[i][j] != null) {
                        ret.append((char) (i) + " - " + (char) (j) + " = " + pathList[i][j].length + " = {");
                        for (int k = 0; k < pathList[i][j].length; k++) {
                            ret.append(pathList[i][j][k] + " ");
                        }
                        ret.append("}\n");
                    }
                }
            }
        }
        return ret;
    }

    public void GenerateAllPairShortestPath(int indexMethod) {
        if (indexMethod == INDEX_ASTAR) {
            for (int i = 0; i < 26; i++) {
                char c = (char) (i + 65);
                if (c != 'P') {
                    Vendor v = vendorList.get(c);
                    if (v != null) {
                        for (int j = i + 1; j < 26; j++) {
                            if (j == i + 1) {
                                pathList[i + 65][i + 65] = new byte[0];
                            }
                            char c2 = (char) (j + 65);
                            Vendor v2 = vendorList.get(c2);
                            if (v2 != null) {
                                pathList[i + 65][j + 65] = pathAStar(v.xPosition, v.yPosition, v2.xPosition, v2.yPosition);
//                                pathList[j + 65][i + 65] = pathList[i + 65][j + 65];
                                pathList[j + 65][i + 65] = pathAStar(v2.xPosition, v2.yPosition, v.xPosition, v.yPosition);
                            }
                        }
                    }
                } else {
                    for (int j = 0; j < 26; j++) {
                        if (j == i + 1) {
                            pathList[i + 65][i + 65] = new byte[0];
                        }
                        char c2 = (char) (j + 65);
                        Vendor v2 = vendorList.get(c2);
                        if (v2 != null) {
                            pathList[80][j + 65] = pathAStar(factory.xPosition, factory.yPosition, v2.xPosition, v2.yPosition);
//                            pathList[j + 65][80] = pathList[80][j + 65];
                            pathList[j+65][80] = pathAStar(v2.xPosition, v2.yPosition, factory.xPosition, factory.yPosition);
                        }
                    }
                }
            }
        } else if (indexMethod == INDEX_BESTFS) {
        } else if (indexMethod == INDEX_BFS) {
            for (int i = 0; i < 26; i++) {
                char c = (char) (i + 65);
                if (c != 'P') {
                    Vendor v = vendorList.get(c);
                    if (v != null) {
                        for (int j = i + 1; j < 26; j++) {
                            if (j == i + 1) {
                                pathList[i + 65][i + 65] = new byte[0];
                            }
                            char c2 = (char) (j + 65);
                            Vendor v2 = vendorList.get(c2);
                            if (v2 != null) {
                                pathList[i + 65][j + 65] = pathBFS(v.xPosition, v.yPosition, v2.xPosition, v2.yPosition);
//                                pathList[j + 65][i + 65] = pathList[i + 65][j + 65];
                                pathList[j + 65][i + 65] = pathBFS(v2.xPosition, v2.yPosition, v.xPosition, v.yPosition);

                            }
                        }
                    }
                } else {
                    for (int j = 0; j < 26; j++) {
                        if (j == i + 1) {
                            pathList[i + 65][i + 65] = new byte[0];
                        }
                        char c2 = (char) (j + 65);
                        Vendor v2 = vendorList.get(c2);
                        if (v2 != null) {
                            pathList[80][j + 65] = pathBFS(factory.xPosition, factory.yPosition, v2.xPosition, v2.yPosition);
//                            pathList[j + 65][80] = pathList[80][j + 65];
                            pathList[j+65][80] = pathBFS(v2.xPosition, v2.yPosition, factory.xPosition, factory.yPosition);

                        }
                    }
                }
            }
        } else if (indexMethod == INDEX_DFS) {
        } else if (indexMethod == INDEX_UCS) {
            for (int i = 0; i < 26; i++) {
                char c = (char) (i + 65);
                if (c != 'P') {
                    Vendor v = vendorList.get(c);
                    if (v != null) {
                        for (int j = i + 1; j < 26; j++) {
                            if (j == i + 1) {
                                pathList[i + 65][i + 65] = new byte[0];
                            }
                            char c2 = (char) (j + 65);
                            Vendor v2 = vendorList.get(c2);
                            if (v2 != null) {
                                pathList[i + 65][j + 65] = pathUCS(v.xPosition, v.yPosition, v2.xPosition, v2.yPosition);
//                                pathList[j + 65][i + 65] = pathList[i + 65][j + 65];
                                pathList[j + 65][i + 65] = pathUCS(v2.xPosition, v2.yPosition, v.xPosition, v.yPosition);

                            }
                        }
                    }
                } else {
                    for (int j = 0; j < 26; j++) {
                        if (j == i + 1) {
                            pathList[i + 65][i + 65] = new byte[0];
                        }
                        char c2 = (char) (j + 65);
                        Vendor v2 = vendorList.get(c2);
                        if (v2 != null) {
                            pathList[80][j + 65] = pathUCS(factory.xPosition, factory.yPosition, v2.xPosition, v2.yPosition);
//                            pathList[j + 65][80] = pathList[80][j + 65];
                            pathList[j+65][80] = pathUCS(v2.xPosition, v2.yPosition, factory.xPosition, factory.yPosition);
                        }
                    }
                }
            }
        }
    }

    public static void main(String args[]) {

        // load file
//        File file = new File("C:\\Users\\Acer\\Desktop\\AI\\Tugas Besar 1 IB\\GA Coordinator\\testcase1.txt");
        File file = new File("D:\\Master Document\\My Documents\\NetBeansProjects\\GA-Coordination\\build\\classes\\input4.txt");
        
        // start GA
        World world = new World(file);
        world.GenerateAllPairShortestPath(INDEX_BFS);
        // world.PrintAllPairShortesPath();
        if (world.map!=null){
            GACoordinator gac = new GACoordinator(world.factory.hour, world.totalAllMachine,
                    world.machineList, world.truckCapacity, world.pathList, world.factory, world.vendorList);

            System.out.println(gac.solveSolution());
            // stop GA
            // output result
            // digenerate dulu,baru bisa di parse di GUI
            if (gac.pathTruckElitism!=null){
                // ada solusi                
                world.truck.generatePath(gac.compactIndividuElitism, gac.pathTruckElitism, world.pathList);
                // DEBUG
//                world.truck.PrintPath();
            }                        
        }
        

    }

    public byte[] pathBFS(int x1, int y1, int x2, int y2) {
        log.append("Path BFS dari " + x1 + ","+y1 + " ke " + x2+","+y2);
        byte retval[] = null;
        ArrayList<TreeNode> nodeQueue = new ArrayList<TreeNode>();
        ArrayDeque<Point> openQueue = new ArrayDeque<Point>();
        TreeNode rootNode = new TreeNode(x1, y1, null);
        HashMap<Point, Boolean> closedMap = new HashMap<Point, Boolean>();

        nodeQueue.add(rootNode);
        openQueue.add(new Point(x1, y1));

        Point solution = null;
        while (!openQueue.isEmpty() && solution == null) {
            Point currentPoint = openQueue.remove();
            log.append("Current " + currentPoint.x + "," + currentPoint.y + " diekspand\n");
            if (!isSolution(currentPoint, x2, y2)) {
                Point expandAtas = new Point(currentPoint.x - 1, currentPoint.y);
                if (closedMap.get(expandAtas) == null && isCanMoveUp(currentPoint)) {
                    openQueue.add(expandAtas);
                    nodeQueue.add(new TreeNode(expandAtas, currentPoint));
                }
                Point expandDown = new Point(currentPoint.x + 1, currentPoint.y);
                if (closedMap.get(expandDown) == null && isCanMoveDown(currentPoint)) {
                    openQueue.add(expandDown);
                    nodeQueue.add(new TreeNode(expandDown, currentPoint));
                }
                Point expandRight = new Point(currentPoint.x, currentPoint.y + 1);
                if (closedMap.get(expandRight) == null && isCanMoveRight(currentPoint)) {
                    openQueue.add(expandRight);
                    nodeQueue.add(new TreeNode(expandRight, currentPoint));
                }
                Point expandLeft = new Point(currentPoint.x, currentPoint.y - 1);
                if (closedMap.get(expandLeft) == null && isCanMoveLeft(currentPoint)) {
                    openQueue.add(expandLeft);
                    nodeQueue.add(new TreeNode(expandLeft, currentPoint));
                }
                closedMap.put(currentPoint, Boolean.TRUE);
            } else {
                solution = currentPoint;
            }
        }

        if (solution != null) {
            TreeNode solutionNode = null;
            for (int i = 0; i < nodeQueue.size(); i++) {
                if (nodeQueue.get(i).node.equals(solution)) {
                    solutionNode = nodeQueue.get(i);
                    break;
                }
            }
            Deque<Byte> pathQueue = new ArrayDeque<Byte>();

            while (!solutionNode.isRoot()) {
                pathQueue.addLast(solutionNode.getDirection());
                for (int i = 0; i < nodeQueue.size(); i++) {
                    if (nodeQueue.get(i).node.equals(solutionNode.parent)) {
                        solutionNode = nodeQueue.get(i);
                        break;
                    }
                }
            }
            retval = new byte[pathQueue.size()];
            int idx = 0;
            while (!pathQueue.isEmpty()) {
                retval[idx] = pathQueue.removeLast();
                idx++;
            }

        } else {
            // no solution
        }        
        return retval;
    }

    public byte[] pathUCS(int x1, int y1, int x2, int y2) {
        log.append("Path UCS dari " + x1 + ","+y1 + " ke " + x2+","+y2);
        byte retval[] = null;
        ArrayList<TreeNode> nodeQueue = new ArrayList<TreeNode>();
        PriorityQueue<CostNode> openQueue = new PriorityQueue<CostNode>();
        TreeNode rootNode = new TreeNode(x1, y1, null);
        HashMap<Point, Boolean> closedMap = new HashMap<Point, Boolean>();

        nodeQueue.add(rootNode);
        openQueue.add(new CostNode(new Point(x1, y1), 0));

        Point solution = null;
        while (!openQueue.isEmpty() && solution == null) {
            CostNode currentNode = openQueue.remove();
            log.append("Current " + currentNode.point.x + "," + currentNode.point.y + "\n");
            if (!isSolution(currentNode.point, x2, y2)) {
                Point expandAtas = new Point(currentNode.point.x - 1, currentNode.point.y);
                if (closedMap.get(expandAtas) == null && isCanMoveUp(currentNode.point)) {
                    openQueue.add(new CostNode(expandAtas, currentNode.value + 1));
                    nodeQueue.add(new TreeNode(expandAtas, currentNode.point));
                }
                Point expandDown = new Point(currentNode.point.x + 1, currentNode.point.y);
                if (closedMap.get(expandDown) == null && isCanMoveDown(currentNode.point)) {
                    openQueue.add(new CostNode(expandDown, currentNode.value + 1));
                    nodeQueue.add(new TreeNode(expandDown, currentNode.point));
                }
                Point expandRight = new Point(currentNode.point.x, currentNode.point.y + 1);
                if (closedMap.get(expandRight) == null && isCanMoveRight(currentNode.point)) {
                    openQueue.add(new CostNode(expandRight, currentNode.value + 1));
                    nodeQueue.add(new TreeNode(expandRight, currentNode.point));
                }
                Point expandLeft = new Point(currentNode.point.x, currentNode.point.y - 1);
                if (closedMap.get(expandLeft) == null && isCanMoveLeft(currentNode.point)) {
                    openQueue.add(new CostNode(expandLeft, currentNode.value + 1));
                    nodeQueue.add(new TreeNode(expandLeft, currentNode.point));
                }
                closedMap.put(currentNode.point, Boolean.TRUE);
            } else {
                solution = currentNode.point;
            }
        }

        if (solution != null) {
            TreeNode solutionNode = null;
            for (int i = 0; i < nodeQueue.size(); i++) {
                if (nodeQueue.get(i).node.equals(solution)) {
                    solutionNode = nodeQueue.get(i);
                    break;
                }
            }
            Deque<Byte> pathQueue = new ArrayDeque<Byte>();

            while (!solutionNode.isRoot()) {
                pathQueue.addLast(solutionNode.getDirection());
                for (int i = 0; i < nodeQueue.size(); i++) {
                    if (nodeQueue.get(i).node.equals(solutionNode.parent)) {
                        solutionNode = nodeQueue.get(i);
                        break;
                    }
                }
            }
            retval = new byte[pathQueue.size()];
            int idx = 0;
            while (!pathQueue.isEmpty()) {
                retval[idx] = pathQueue.removeLast();
                idx++;
            }

        } else {
            // no solution
        }        
        return retval;
    }

    public byte[] pathAStar(int x1, int y1, int x2, int y2) {
        log.append("Path AStar dari " + x1 + ","+y1 + " ke " + x2+","+y2);
        byte retval[] = null;
        ArrayList<TreeNode> nodeQueue = new ArrayList<TreeNode>();
        PriorityQueue<CostNode> openQueue = new PriorityQueue<CostNode>();
        TreeNode rootNode = new TreeNode(x1, y1, null);
        HashMap<Point, Boolean> closedMap = new HashMap<Point, Boolean>();

        nodeQueue.add(rootNode);
        openQueue.add(new CostNode(new Point(x1, y1), 0));

        Point solution = null;
        while (!openQueue.isEmpty() && solution == null) {
            CostNode currentNode = openQueue.remove();
            log.append("Current " + currentNode.point.x + "," + currentNode.point.y);
            if (!isSolution(currentNode.point, x2, y2)) {
                Point expandAtas = new Point(currentNode.point.x - 1, currentNode.point.y);
                if (closedMap.get(expandAtas) == null && isCanMoveUp(currentNode.point)) {
                    openQueue.add(new CostNode(expandAtas, currentNode.value + 1 + (float) manhattanHeuristic(expandAtas, x2, y2)));
                    nodeQueue.add(new TreeNode(expandAtas, currentNode.point));
                }
                Point expandDown = new Point(currentNode.point.x + 1, currentNode.point.y);
                if (closedMap.get(expandDown) == null && isCanMoveDown(currentNode.point)) {
                    openQueue.add(new CostNode(expandDown, currentNode.value + 1 + (float) manhattanHeuristic(expandDown, x2, y2)));
                    nodeQueue.add(new TreeNode(expandDown, currentNode.point));
                }
                Point expandRight = new Point(currentNode.point.x, currentNode.point.y + 1);
                if (closedMap.get(expandRight) == null && isCanMoveRight(currentNode.point)) {
                    openQueue.add(new CostNode(expandRight, currentNode.value + 1 + (float) manhattanHeuristic(expandRight, x2, y2)));
                    nodeQueue.add(new TreeNode(expandRight, currentNode.point));
                }
                Point expandLeft = new Point(currentNode.point.x, currentNode.point.y - 1);
                if (closedMap.get(expandLeft) == null && isCanMoveLeft(currentNode.point)) {
                    openQueue.add(new CostNode(expandLeft, currentNode.value + 1 + (float) manhattanHeuristic(expandLeft, x2, y2)));
                    nodeQueue.add(new TreeNode(expandLeft, currentNode.point));
                }
                closedMap.put(currentNode.point, Boolean.TRUE);
            } else {
                solution = currentNode.point;
            }
        }

        if (solution != null) {
            TreeNode solutionNode = null;
            for (int i = 0; i < nodeQueue.size(); i++) {
                if (nodeQueue.get(i).node.equals(solution)) {
                    solutionNode = nodeQueue.get(i);
                    break;
                }
            }
            Deque<Byte> pathQueue = new ArrayDeque<Byte>();

            while (!solutionNode.isRoot()) {
                pathQueue.addLast(solutionNode.getDirection());
                for (int i = 0; i < nodeQueue.size(); i++) {
                    if (nodeQueue.get(i).node.equals(solutionNode.parent)) {
                        solutionNode = nodeQueue.get(i);
                        break;
                    }
                }
            }
            retval = new byte[pathQueue.size()];
            int idx = 0;
            while (!pathQueue.isEmpty()) {
                retval[idx] = pathQueue.removeLast();
                idx++;
            }

        } else {
            // no solution
        }
        return retval;
    }

    public double manhattanHeuristic(Point P, int xG, int yG) {
        int x = P.x;
        int y = P.y;
        return Math.sqrt((xG - x) * (xG - x) + (yG - y) * (yG - y));

    }

    public static class TreeNode {

        public Point node;
        public Point parent;

        public TreeNode() {
        }

        public TreeNode(int x, int y, Point parent) {
            this.node = new Point(x, y);
            this.parent = parent;
        }

        public TreeNode(Point node, Point parent) {
            this.node = node;
            this.parent = parent;
        }

        public boolean isRoot() {
            return parent == null;
        }

        @Override
        public String toString() {
            if (parent == null) {
                return "(" + node.x + "," + node.y + ") null";
            } else {
                return "(" + node.x + "," + node.y + ")" + parent;
            }
        }

        public byte getDirection() {
            if (!isRoot()) {
                int x1 = parent.x;
                int y1 = parent.y;
                int x2 = node.x;
                int y2 = node.y;
                if (x2 > x1) {
                    return PATH_DOWN;
                } else if (x2 < x1) {
                    return PATH_UP;
                } else if (y2 > y1) {
                    return PATH_RIGHT;
                } else {
                    return PATH_LEFT;
                }
            } else {
                return 9;
            }
        }
    }

    public static class CostNode implements Comparator<CostNode>, Comparable<CostNode> {

        public Point point;
        public Float value;

        public CostNode() {
        }

        public CostNode(Point point, float value) {
            this.point = point;
            this.value = value;
        }

        @Override
        public int compareTo(CostNode o) {
            return this.value.compareTo(o.value);
        }

        @Override
        public int compare(CostNode o1, CostNode o2) {
            return (int) (o1.value - o2.value);
        }
    }

    public StringBuffer PrintAllMachine() {
        StringBuffer ret = new StringBuffer("Machine\n");
        System.out.println("Machine");
        for (int i = 0; i < totalAllMachine; i++) {
            System.out.println(machineList[i]);
            ret.append(machineList[i]);
            ret.append('\n');

        }
        return ret;
    }

    public void PrintAllVendor() {
        Set<Character> keySet = vendorList.keySet();
        System.out.println("Vendor");
        for (char c : keySet) {
            System.out.println(vendorList.get(c));
        }
    }

    public void PrintFactory() {
        System.out.println(factory);
    }

    public void PrintMap() {
        for (int i = 0; i < rowMap; i++) {
            for (int j = 0; j < columnMap; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    public boolean isSolution(Point p, int xG, int yG) {
        int x = p.x;
        int y = p.y;
        return x == xG && y == yG;
    }

    public boolean isCanMoveUp(Point p) {
        int x = p.x;
        int y = p.y;
        if (x > 0) {
            return map[x - 1][y] != '#';
        } else {
            return false;
        }
    }

    public boolean isCanMoveDown(Point p) {
        int x = p.x;
        int y = p.y;
        if (x < rowMap - 1) {
            return map[x + 1][y] != '#';
        } else {
            return false;
        }
    }

    public boolean isCanMoveLeft(Point p) {
        int x = p.x;
        int y = p.y;
        if (y > 0) {
            return map[x][y - 1] != '#';
        } else {
            return false;
        }
    }

    public boolean isCanMoveRight(Point p) {
        int x = p.x;
        int y = p.y;
        if (y < columnMap - 1) {
            return map[x][y + 1] != '#';
        } else {
            return false;
        }
    }
    
    public StringBuffer Log (){
        StringBuffer ret = new StringBuffer("LOG\nPATH\n");        
        ret.append(log);
        ret.append('\n');        
        return ret;
    }
    
}
